Network of Schools

Dec 16, 2024 11:44 AM
Dec 17, 2024 4:34 AM

Destription

许多学校都与计算机网络相连。这些学校之间已达成协议:每所学校都有一份向其分发软件的学校名单(“接收学校”)。注意,如果 B 在学校 A 的分发列表中,则 A 不一定出现在学校 B 的列表中

你要编写一个程序,计算必须收到新软件副本的学校的最小数量,以便软件根据协议到达网络中的所有学校(子任务 A)。作为进一步的任务,我们要确保通过向任意学校发送新软件的副本,该软件将到达网络中的所有学校。为了实现这一目标,我们可能需要增加新成员的接收者名单。计算必须进行的最小扩展数量,以便我们将新软件发送到任何学校,它将到达所有其他学校(子任务 B)。一个扩展意味着在一所学校的接收者名单中引入一个新成员。

Input

第一行包含整数 N:网络中的学校数量(2N100)。学校由前 N 个正整数标识。接下来的 N 行中的每一行描述接收器列表。行 i+1 包含学校 i 的接收者的标识符。每个列表都以 0 结尾。一个空列表只在一行中包含一个0

Output

第一行应该包含一个正整数:子任务 A 的解。第二行应该包含子任务 B 的解决方案。

Sample Input

5
2 4 3 0
4 5 0
0
0
1 0

Sample Output

1
2

问题在于如何理解 ans1 ans2
ans1=cnt(!rdu[i]) ans2=max(ans1,!cdu[i])

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, dfn[N], low[N], tot, cnt, scc[N], siz[N], top, instk[N], stk[N], cdu[N], rdu[N];
vector<int> e[N];
void tarjan(int x)
{
    dfn[x] = low[x] = ++tot;
    stk[++top] = x;
    instk[x] = 1;

    for (int y : e[x])
    { //邻接表存图
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (instk[y])
        {
            low[x] = min(low[x], low[y]);
        }
    }

    if (dfn[x] == low[x])
    {
        int y;
        ++cnt;
        do
        {
            y = stk[top--];
            instk[y] = 0;
            scc[y] = cnt;
            ++siz[cnt];
        } while (y != x);
    }
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        while (cin >> x && x)
            e[i].push_back(x);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
/*-------------------------------*/
    for (int i = 1; i <= n; i++)
    {
        for (auto v : e[i])
        {
            if (scc[i] != scc[v])
            {
                cdu[scc[i]]++;
                rdu[scc[v]]++;
            }
        }
    }
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= cnt; i++)
    {
        if (!cdu[i])
            cnt2++;
        if (!rdu[i])
            cnt1++;
    }
    cout << cnt1 << '\n'
         << max(cnt1, cnt2) << '\n';
/*--------------------------------*/
}